//链表 - 重排链表

class Solution {
public:
    void reorderList(ListNode* head) {
        //1.找中间节点
        ListNode* fast = head, *slow = head;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }

        //2.后半部分逆序
        ListNode* newHead = new ListNode(-1);
        ListNode* cur = slow->next;
        slow->next = nullptr;
        while(cur)
        {
            ListNode* next = cur->next;
            cur->next = newHead->next;
            newHead->next = cur;
            cur = next;
        }
        
        //3.合并两个链表
        ListNode* retHead = new ListNode(-1);
        ListNode* cur1 = head, *cur2 = newHead->next;
        ListNode* tail = retHead;
        while(cur1)
        {
            tail->next = cur1;
            cur1 = cur1->next;
            tail = tail->next;
            if(cur2)
            {
                tail->next = cur2;
                cur2 = cur2->next;
                tail = tail->next;
            }
        }
        delete newHead;
        delete retHead;
    }
};


